package com.lft.tree09.self_balanceing_bst;

/**
 * AVL 平衡二叉排序树
 */
public class SelfBalanceingBST {
	public static void main(String[] args) {
		int[] a = {10, 11, 7, 6, 8, 9, 1, 2, 3, 4, 5};
		// 创建 AVLTree 对象
		AVLTree avlTree = new AVLTree();
		for (int i = 0; i < a.length; i++) {
			avlTree.add(new Node(a[i]));
		}
		
		// 中序遍历
		
		avlTree.infixOrder();
		
		// 打印树结构
		TreeOperation.show(avlTree.getRoot());
		
		// 输出树的高度
		System.out.println(avlTree.getRoot().getTreeHeight());
		// 输出左子树的高度
		System.out.println(avlTree.getRoot().getLeftTreeHeight());
		// 输出右子树的高度
		System.out.println(avlTree.getRoot().getRightTreeHeight());
		
		System.out.println(avlTree.getRoot());
		
		// avlTree.fixup(avlTree.getRoot());
		
		// 打印树结构
		// TreeOperation.show(avlTree.getRoot());
	}
}

class AVLTree {
	private Node root;
	
	/**
	 * 添加节点
	 * @param node 要添加的节点
	 */
	public void add(Node node) {
		if (node == null) {
			return;
		}
		if (root == null) {
			// 如果 root 为空，则直接让 root 指向 node
			root = node;
		} else {
			root.add(node);
		}
		// 添加好之后。判断调整
		if (this.getRoot().getRightTreeHeight() - this.getRoot().getLeftTreeHeight() > 1) {
			if (this.getRoot().getLeft() != null &&
					this.getRoot().getRight().getLeftTreeHeight() > this.getRoot().getRight().getRightTreeHeight()) {
				// 先对当前结点的右结点 -> 右旋转
				rightRotate(this.getRoot().getRight());
				// 再左旋转
				leftRotate(this.getRoot());
			} else {
				leftRotate(this.getRoot());
			}
			return;
		}
		if (this.getRoot().getLeftTreeHeight() - this.getRoot().getRightTreeHeight() > 1) {
			if (this.getRoot().getLeft() != null &&
					this.getRoot().getLeft().getRightTreeHeight() > this.getRoot().getLeft().getLeftTreeHeight()) {
				// 先对当前结点的左结点 -> 左旋转
				leftRotate(this.getRoot().getLeft());
				// 再右旋转
				rightRotate(this.getRoot());
			} else {
				rightRotate(this.getRoot());
			}
			return;
		}
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void setRoot(Node root) {
		this.root = root;
	}
	
	/**
	 * 查找要删除的节点
	 * @param value 要删除的节点的值
	 * @return 找到返回该节点，否则返回null
	 */
	public Node searchNode(int value) {
		if (root == null) {
			return null;
		} else {
			return root.searchNode(value);
		}
	}
	
	/**
	 * 查找传入节点的父节点
	 * @param node 要查找父节点的当前节点
	 * @return 返回传入节点的父节点，否则返回null
	 */
	public Node searchParentNode(Node node) {
		if (root == null || node == null) {
			return null;
		} else {
			return root.searchParentNode(node);
		}
	}
	
	/**
	 * 删除节点
	 * @param value 要删除节点的值
	 */
	public void deleteNode(int value) {
		if (root == null) {
			return;
		}
		// 找到要删除的节点
		Node targetNode = searchNode(value);
		// 没有找到要删除的节点
		if (targetNode == null) {
			return;
		}
		// 找到要删除节点的父节点
		Node parent = searchParentNode(targetNode);
		if (parent == null) {
			// targetNode 没有父节点，两种情况：1是根节点，2是二叉排序树中没有这个节点。
			// 【情况一】要删除的节点是根节点。且根节点没有左右子树。
			// 没有左右子树，且当前节点的值跟要删除节点的值一样。则直接将root置空。
			if (root.getValue() == value && root.getLeft() == null && root.getRight() == null) {
				root = null;
				return;
			}
			// 【情况二】要删除的节点是根节点。有左子树，有没有右子树无所谓。
			// 如果有左子树，且当前节点的值跟要删除节点的值一样。左子树不为空，则找左子树最大的。或者找右子树最小的。
			if (root.getLeft() != null && root.getValue() == value) {
				Node temp = root.getLeft();
				Node fast = temp;
				Node slow;
				// 如果 fast 在右侧为空，那 fast 就是左侧最大的。直接把原 root 的右侧赋值给 fast 右侧。再root 指向 fast
				if (fast.getRight() == null) {
					fast.setRight(root.getRight());
					// 将原有的 root 左右置空。原 root 节点就游离等待回收。
					root.setRight(null);
					root.setLeft(null);
					root = fast;
				}
				// fast 的右侧不为空。找到最大的。
				else {
					while (true) {
						if (fast.getRight().getRight() == null) {
							slow = fast;
							fast = fast.getRight();
							slow.setRight(fast.getLeft());
							fast.setRight(root.getRight());
							fast.setLeft(temp);
							root = fast;
							break;
						} else {
							slow = fast;
							fast = fast.getRight();
						}
					}
				}
			}
			// 【情况三】要删除的节点是根节点。没有左子树，有右子树。
			// 没有左子树，是有右子树
			if (root.getLeft() == null && root.getRight() != null && root.getValue() == value) {
				Node temp = root.getRight();
				Node fast = temp;
				Node slow;
				// 如果 fast 在左侧为空，那 fast 就是右侧最小的。直接把原 root 的左侧赋值给 fast 左侧。再root 指向 fast
				if (fast.getLeft() == null) {
					fast.setLeft(root.getLeft());
					// 将原有的 root 左右置空。原 root 节点就游离等待回收。
					root.setRight(null);
					root.setLeft(null);
					root = fast;
				}
				// fast 的左侧不为空。找到最小的。
				else {
					while (true) {
						if (fast.getLeft().getLeft() == null) {
							slow = fast;
							fast = fast.getLeft();
							slow.setLeft(fast.getRight());
							fast.setLeft(root.getLeft());
							fast.setRight(temp);
							root = fast;
							break;
						} else {
							slow = fast;
							fast = fast.getLeft();
						}
					}
				}
			}
		} else {
			// 【情况四】：要删除的不是根节点——要删除的节点是叶子节点
			if (targetNode.getLeft() == null && targetNode.getRight() == null) {
				if (targetNode == parent.getLeft()) {
					parent.setLeft(null);
				}
				if (targetNode == parent.getRight()) {
					parent.setRight(null);
				}
			}
			// 【情况五】要删除的节点有一棵子树
			// 【情况五-1】目标节点是父节点的左子节点，且目标节点有一个左子节点。
			if (parent.getLeft() == targetNode && targetNode.getLeft() != null && targetNode.getRight() == null) {
				parent.setLeft(targetNode.getLeft());
				targetNode.setLeft(null);
			}
			// 【情况五-2】目标节点是父节点的左子节点，且目标节点有一个右子节点。
			if (parent.getLeft() == targetNode && targetNode.getLeft() == null && targetNode.getRight() != null) {
				parent.setLeft(targetNode.getRight());
				targetNode.setRight(null);
			}
			// 【情况五-3】目标节点是父节点的右子节点，且目标节点有一个左子节点。
			if (parent.getRight() == targetNode && targetNode.getLeft() != null && targetNode.getRight() == null) {
				parent.setRight(targetNode.getLeft());
				targetNode.setLeft(null);
			}
			// 【情况五-4】目标节点是父节点的右子节点，且目标节点有一个右子节点。
			if (parent.getRight() == targetNode && targetNode.getLeft() == null && targetNode.getRight() != null) {
				parent.setRight(targetNode.getRight());
				targetNode.setRight(null);
			}
			// 【情况六】目标节点有两棵子树的节点
			// 【情况六-1】目标节点有两棵子树的节点，且是父节点的左子节点。
			if (parent.getLeft() == targetNode && targetNode.getLeft() != null && targetNode.getRight() != null) {
				Node temp = targetNode.getLeft();
				Node fast = temp;
				Node slow;
				if (fast.getRight() == null) {
					fast.setRight(targetNode.getRight());
					targetNode.setRight(null);
					targetNode.setLeft(null);
					parent.setLeft(fast);
				} else {
					while (true) {
						if (fast.getRight().getRight() == null) {
							slow = fast;
							fast = fast.getRight();
							slow.setRight(fast.getLeft());
							fast.setRight(targetNode.getRight());
							fast.setLeft(temp);
							break;
						} else {
							slow = fast;
							fast = fast.getRight();
						}
					}
				}
			}
			// 【情况六-2】目标节点有两棵子树的节点，且是父节点的右子节点。
			if (parent.getRight() == targetNode && targetNode.getLeft() != null && targetNode.getRight() != null) {
				Node temp = targetNode.getLeft();
				Node fast = temp;
				Node slow;
				if (fast.getRight() == null) {
					fast.setRight(targetNode.getRight());
					targetNode.setRight(null);
					targetNode.setLeft(null);
					parent.setRight(fast);
				} else {
					while (true) {
						if (fast.getRight().getRight() == null) {
							slow = fast;
							fast = fast.getRight();
							slow.setRight(fast.getLeft());
							fast.setRight(targetNode.getRight());
							fast.setLeft(temp);
							break;
						} else {
							slow = fast;
							fast = fast.getRight();
						}
					}
				}
			}
		}
	}
	
	/**
	 * 左旋方法
	 */
	public void leftRotate(Node node) {
		// 传入的节点为空，直接返回
		if (node == null) {
			return;
		}
		// 1. 创建临时新节点,指向当前节点的右节点。
		Node newNode = node.getRight();
		// 如果右子节点为空，直接返回
		if (newNode == null) {
			return;
		}
		// 2. 把新节点的左子树，设置为当前节点的左子树。
		node.setRight(newNode.getLeft());
		// 3. 把原来的节点设置为新节点的左子节点。
		newNode.setLeft(node);
		Node parentNode = this.searchParentNode(node);
		// 如果父节点是空，说明当前节点是根节点。或者没有这个节点
		if (parentNode == null) {
			// 没有这个节点
			if (this.getRoot() != node) {
				return;
			}
			// 这个节点就是根节点
			else {
				// 将根节点设置为这个新节点。
				this.setRoot(newNode);
			}
		}
		// 父节点不为空。
		else {
			// 原来的节点是父节点的左子节点。
			if (parentNode.getLeft() == node) {
				parentNode.setLeft(newNode);
			} else {
				parentNode.setRight(newNode);
			}
		}
	}
	
	/**
	 * 右旋方法
	 */
	public void rightRotate(Node node) {
		// 传入的节点为空，直接返回
		if (node == null) {
			return;
		}
		// 1. 创建临时新节点,指向当前节点的右节点。
		Node newNode = node.getLeft();
		// 如果右子节点为空，直接返回
		if (newNode == null) {
			return;
		}
		// 2. 把新节点的左子树，设置为当前节点的左子树。
		node.setLeft(newNode.getRight());
		// 3. 把原来的节点设置为新节点的左子节点。
		newNode.setRight(node);
		Node parentNode = this.searchParentNode(node);
		// 如果父节点是空，说明当前节点是根节点。或者没有这个节点
		if (parentNode == null) {
			// 没有这个节点
			if (this.getRoot() != node) {
				return;
			}
			// 这个节点就是根节点
			else {
				// 将根节点设置为这个新节点。
				this.setRoot(newNode);
			}
		}
		// 父节点不为空。
		else {
			// 原来的节点是父节点的左子节点。
			if (parentNode.getLeft() == node) {
				parentNode.setLeft(newNode);
			} else {
				parentNode.setRight(newNode);
			}
		}
	}
	
	/**
	 * 平衡方法
	 * @param node
	 */
	public void fixup(Node node) {
		if (node == null) {
			return;
		}
		Node leftFast = node.getLeft();
		Node leftSlow = node;
		Node rightFast = node.getRight();
		Node rightSlow = node;
		
		// 遍历到最左侧
		while (leftFast.getLeft().getLeft() != null) {
			leftSlow = leftFast;
			leftSlow = leftFast.getLeft();
		}
		if (leftSlow.getRightTreeHeight() - leftSlow.getLeftTreeHeight() > 1) {
		
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
		} else {
			System.out.println("二叉排序树为空！！无法遍历！！");
		}
	}
}

/**
 * 节点类
 */
class Node {
	private int value;
	private Node left;
	private Node right;
	
	public Node(int value) {
		this.value = value;
	}
	
	/**
	 * 添加节点的方法
	 * 递归的形式添加节点，注意需要满足二叉排序树的要求
	 * @param node
	 */
	public void add(Node node) {
		if (node == null) {
			return;
		}
		// 判断传入节点的值，和当前子树根节点的值的关系。
		if (node.getValue() <= this.getValue()) {
			// 当前节点的左子节点为空。
			if (this.getLeft() == null) {
				this.setLeft(node);
			} else {
				// 如果当前节点的左子节点不为空，就递归查找。
				this.getLeft().add(node);
			}
		}
		// 要添加的节点的值，大于当前节点的值。
		else {
			// 如果当前节点的右子节点为空。
			if (this.getRight() == null) {
				this.setRight(node);
			} else {
				// 如果当前节点的右子节点不为空，就递归找到要添加的位置。
				this.getRight().add(node);
			}
		}
		
	}
	
	/**
	 * 查找要删除的节点
	 * @param value 希望删除的节点的值
	 * @return 找到返回该节点。否则返回 null
	 */
	public Node searchNode(int value) {
		// 找到就是当前结点
		if (value == this.getValue()) {
			return this;
		}
		// 如果查找的值小于当前节点，向左子树递归查找。
		else if (value <= this.getValue()) {
			if (this.getLeft() != null) {
				return this.getLeft().searchNode(value);
			} else {
				return null;
			}
		}
		// 如果查找的值大于当前节点，向右子树递归查找。
		else {
			if (this.getRight() != null) {
				return this.getRight().searchNode(value);
			} else {
				return null;
			}
		}
	}
	
	/**
	 * 查找当前节点的父节点
	 * @param node 要找到的节点的值
	 * @return 返回要删除节点的父节点，如果没有就返回 null
	 */
	public Node searchParentNode(Node node) {
		// 传入为空
		if (node == null) {
			return null;
		} else if (node.getValue() == this.getValue()) {
			return null;
		}
		// 要查找的值小于当前节点的值。
		else if (node.getValue() < this.getValue()) {
			// 左子节点不为空。
			if (this.getLeft() != null) {
				// 左子节点的值跟要查找的值相等，就返回当前节点是要查找节点的父节点。
				if (this.getLeft().getValue() == node.getValue()) {
					return this;
				}
				// 递归往左查找。
				else {
					return this.getLeft().searchParentNode(node);
				}
			}
			// 左子节点为空，返回 null
			else {
				return null;
			}
		}
		// 要查找的值大于当前节点的值。
		else {
			// 右子节点不为空。
			if (this.getRight() != null) {
				// 右子节点的值跟要查找的值相等，就返回当前节点是要查找节点的父节点。
				if (this.getRight().getValue() == node.getValue()) {
					return this;
				}
				// 递归往右查找。
				else {
					return this.getRight().searchParentNode(node);
				}
			}
			// 右子节点为空，返回 null
			else {
				return null;
			}
		}
	}
	
	/**
	 * 返回以当前节点为根节点的树的高度。
	 * @return 树的高度。
	 */
	public int getTreeHeight() {
		return Math.max(
				this.getLeft() == null ? 0 : this.getLeft().getTreeHeight(),
				this.getRight() == null ? 0 : this.getRight().getTreeHeight()) + 1;
	}
	
	/**
	 * 返回以当前节点为根节点的左子树的高度。
	 * @return
	 */
	public int getLeftTreeHeight() {
		if (this.getLeft() == null) {
			return 0;
		} else {
			return this.getLeft().getTreeHeight();
		}
	}
	
	/**
	 * 返回以当前节点为根节点的右子树的高度。
	 * @return
	 */
	public int getRightTreeHeight() {
		if (this.getRight() == null) {
			return 0;
		} else {
			return this.getRight().getTreeHeight();
		}
	}
	
	/**
	 * 中序遍历
	 */
	public void infixOrder() {
		// 遍历左子树。
		if (this.getLeft() != null) {
			this.getLeft().infixOrder();
		}
		// 输出当前节点。
		System.out.println(this);
		// 遍历右子树
		if (this.getRight() != null) {
			this.getRight().infixOrder();
		}
	}
	
	public int getValue() {
		return value;
	}
	
	public void setValue(int value) {
		this.value = value;
	}
	
	public Node getLeft() {
		return left;
	}
	
	public void setLeft(Node left) {
		this.left = left;
	}
	
	public Node getRight() {
		return right;
	}
	
	public void setRight(Node right) {
		this.right = right;
	}
	
	@Override
	public String toString() {
		return "Node [" + "value=" + value + ']';
	}
}